package algorithm_demo.leetcode;

import java.util.Arrays;

/**
 * 5. 最长回文子串
 * <a href="https://leetcode.cn/problems/longest-palindromic-substring/?favorite=2cktkvj"></a>
 *
 * @author Api
 * @date 2023/4/9 11:44
 */
public class Problem_0005_LongestPalindromicSubstring {

    /*伪代码*/
   /* public static int maxPLen(String str){
        //"12321"->"#1#2#3#2#1"
        str -> strX;
        int[] pArr = new int[strx.length];
        int R = -1;
        int C = -1;
        for(int i = 0; i< strx.length;i++){
            if(i在R外){
                暴力扩//R变大
            }else{//i在R内
                if(i在对称点的回文区域彻底在L..R内部){
                    pArr[i] = pArr[i对称点];
                }else if (i对称点的回文区域跑到L..R外部){
                    pArr[i] = i - R;
                }else{//i对称点的回文区域左边界和L压线
                    从R外开始扩;//R变大
                }
            }
        }
        return pArr最大值/2;
    }*/



    /*
     * 给你一个字符串 s，找到 s 中最长的回文子串。
     * 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
     */
    /*Manacher算法*/

    public static int manacher(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        //"12132" -> "#1#2#1#3#2#"
        char[] str = manacherString(s);
        //回文半径的大小
        int[] pArr = new int[str.length];
        int C = -1;
        int R = -1;//讲述中：R代表最右扩成功的位置。代码中：最右的扩成功位置的，再下一个位置
        int max = Integer.MIN_VALUE;
        for (int i = 0; i != str.length; i++) {
            //R第一个违规的位置 i>=R
            //i位置扩出来的答案，i位置扩的区域，至少是多大
            //pArr[2 * C - i] i的对称点的区域
            pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : i;
            while (i + pArr[i] < str.length && i - pArr[i] > -1) {
                if (str[i + pArr[i]] == str[i - pArr[i]]) {
                    pArr[i]++;
                } else {
                    break;
                }
            }
            if (i + pArr[i] > R) {
                R = i + pArr[i];
                C = i;
            }
            max = Math.max(max, pArr[i]);
        }
        //如果pArr存放的是回文直径，则结果是max/2，如果是存放的是回文半径，则max-1
        return max - 1;
    }


    //使用manacher算法,返回字符串
    public static String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        char[] str = manacherString(s);
        int[] pArr = new int[str.length];
        int C = -1;
        int R = -1;
        int mid = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i != str.length; i++) {
            pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : i;
            while (i + pArr[i] < str.length && i - pArr[i] > -1) {
                if (str[i + pArr[i]] == str[i - pArr[i]]) {
                    pArr[i]++;
                } else {
                    break;
                }
            }
            if (i + pArr[i] > R) {
                R = i + pArr[i];
                C = i;
            }
            if (max < pArr[i]){
                max = pArr[i];
                mid = i;
            }
        }
        mid = (mid-1)/2;
        max = max -1;
        return s.substring((max & 1) == 0? mid-(max/2)+1:mid-(max/2), mid+(max/2)+1);
    }


    public static char[] manacherString(String str) {
        char[] charArr = str.toCharArray();
        char[] res = new char[str.length() * 2 + 1];
        int index = 0;
        for (int i = 0; i != res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : charArr[index++];
        }
        return res;
    }



    /*中心扩散法*/
    public static String longestPalindrome1(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        int strLen = s.length();
        int left = 0;
        int right = 0;
        int len = 1;
        int maxStart = 0;
        int maxLen = 0;
        for (int i = 0; i < strLen; i++) {
            left = i-1;
            right = i+1;
            //左扩
            while(left>=0 && s.charAt(left) == s.charAt(i)){
                len++;
                left--;
            }
            //右扩
            while(right< strLen && s.charAt(right) == s.charAt(i)){
                len++;
                right++;
            }
            while(left>=0 && right < strLen && s.charAt(right) == s.charAt(left)){
                len = len+2;
                left--;
                right++;
            }
            if (len > maxLen){
                maxLen = len;
                maxStart = left;
            }
            len = 1;
        }
        return s.substring(maxStart + 1, maxStart + maxLen + 1);
    }




    public static String longestPalindrome2(String s) {
        if (s == null || s.length() == 0){
            return "";
        }
        int left = 0;
        int right = 0;
        int maxLen = 0;
        int len = 1;
        int maxStart = 0;
        int strLen = s.length();
        for(int i = 0; i < strLen; i++){
            left = i-1;
            right = i+1;
            while(left >= 0 && s.charAt(left) == s.charAt(i)){
                left--;
                len++;
            }
            while(right<strLen && s.charAt(right) == s.charAt(i)){
                right++;
                len++;
            }
            while(left>=0 && right<strLen && s.charAt(left) == s.charAt(right)){
                right++;
                left--;
                len = len+2;
            }
            if (len> maxLen){
                maxLen = len;
                maxStart = left;
            }
            len = 1;
        }
        return s.substring(maxStart+1, maxStart+maxLen+1);
    }

    public static void main(String[] args) {
        String babad = longestPalindrome2("babad");
        String babad1 = longestPalindrome("babad");
        System.out.println(babad);
        System.out.println(babad1);
    }


}
